#ifndef BINARYTREE_H
#define BINARYTREE_H

#define BT_RED      true
#define BT_BLACK    false

// 结点
struct ST_NODE
{
    int             value;  // 值
    unsigned int    count;  // 重复计数
    bool            color;  // true红色 false黑色
    ST_NODE*        pLeft;  // 左子结点
    ST_NODE*        pRight; // 右子结点
    ST_NODE*        pParent;// 父结点
};

class BinaryTree
{
public:
    BinaryTree();
    ~BinaryTree();

// 外部接口
public:
    void clear();
    void insert(const int& value);
    bool empty();
    bool remove(const int& value);
    // 查找指定元素，返回元素重复次数，不存在返回0
    unsigned int find(const int& value);
    // 遍历，type指定遍历方式，1前序、0中序、-1后续
    void traversal(const short &type) const;

protected:
    // 删除指定结点下全部结点
    void remove(ST_NODE*& pNode);
    // 按指定方式遍历指定结点
    void traversal(const ST_NODE* pNode, const short& type) const;
    // 在指定父结点下寻找指定结点
    ST_NODE* find(const int& value, ST_NODE* pParent);
    // 在指定父结点下寻找值最小结点
    ST_NODE* findMin(ST_NODE* pParent) const;
    // 左旋
    void rotateLeft(ST_NODE* pNode);
    // 右旋
    void rotateRight(ST_NODE* pNode);
    // 修正插入结点
    void insertFixup(ST_NODE* pNode);
    // 修正删除结点
    void deleteFixup(ST_NODE *pNode);

private:
    ST_NODE*    m_pRoot;
    int         m_nodeNum;
};

#endif // BINARYTREE_H
